A video coder is illustrated in FIG. 1. The video coder 10 operates in accordance with CCITT recommendation H.261 (See "Draft Revision of Recommendation H.261 Video Codec for Audio Visual Services at px64 Kbits/sec", Signal Processing: Image Communication 2 (1990) 221-239, Elsevier).
The video coder contains an input frame memory 12 for storing a current frame of video to be coded. The current frame of video is coded on a block-by-block basis. Some frames are coded in accordance with an intra-mode. In the intra-coding mode, no information from a previous frame is utilized and the coding relies entirely on information contained within the current frame. In the intra-mode, the current frame is divided into N.times.N pixel blocks, where N=16 for example. Each block of pixels is transmitted from the memory 12, via the multiplexer 14, to the Discrete Cosine Transform (DCT) circuit 16. In the DCT circuit 16, the Discrete Cosine Transform is applied to the block of pixels. The transformed pixels are then thresholded and quantized in the quantizer circuit 18. The quantized, transformed pixels are then coded using the variable length coder (VLC) 20. The variable length coded pixels are then transmitted via the multiplexer 22 to the buffer 24. The coded pixels are then transmitted from the buffer 24 via a channel 26 to a particular destination, where the pixels are decoded. Depending on the contents of the buffer 24, as well as depending on the transformed pixel values, the quantization controller 27 may vary the threshold and quantization stepsize utilized by the quantizer circuit 18. Information as to the threshold and quantization stepsize used to code a particular block is transmitted to the destination via line 23, the multiplexer 22, the buffer 24, and the channel 26.
The output of the quantizer circuit 18 is connected to the inverse quantizer circuit 28 and Inverse Discrete Cosine Transform (IDCT) circuit. 29. These two circuits serve to reconstruct a block of pixels coded according to the intra-mode. The reconstructed block of pixels is stored in a previous frame memory system 30. Thus, on a block-by-block basis, the entire current frame, in reconstructed form, is stored in the previous frame memory system 30. This insures that when the next frame is coded, the immediately previously coded frame is always available. Note that when a block of pixels is coded using the intra-mode, the multiplexer 37 outputs zero so the adder 34 adds nothing to the output of the IDCT circuit 29. Thus, the output of the IDCT circuit 29 is connected directly to the previous frame memory system 30, without change. When a frame is coded in the intra-mode, all of the blocks in that frame are coded in the manner described above.
Some frames are coded using a technique known as predictive mode coding. When a frame is coded using the predictive mode, some blocks are coded using the intra-mode described above and some blocks are coded using an inter-mode described below. The inter-mode requires information from both the previous frame and the current frame. For a frame coded using the predictive mode, a decision as to whether to use the inter or intra-mode is made on a block-by-block basis.
The first step in deciding whether to use the intra-mode or the inter-mode for a current block is to first find the best match of the current block in the previous frame. For this purpose the processor circuit 300 is used. The processor circuit 300 contains a Motion Estimation Unit (MEU) 31, a Motion Compensation (MC) Decision Unit 32, and an Inter/Intra Decision Unit 33. The current block of the current frame is transmitted from the input frame memory 12 to the MEU 31. A search window of the previous frame, which previous frame is stored in the previous frame memory system 30, is also transmitted to the MEU circuit 31. The search window of the previous frame includes the pixels of the previous frame which correspond to the pixels of the current block of the current frame as well as additional pixels in each dimension to define a search window.
For example, the search window comprises the pixels in the previous frame which correspond to the 16.times.16 current block as well as .+-.7 pixels in each dimension. The error between the 16.times.16 current block and each possible 16.times.16 block in the search window is then determined. The error between the current block at each possible 16.times.16 block in the search window is determined according to the formula ##EQU1## where a(i,j) is a pixel from the current block, b(i-m,j-n) is a pixel from a specific block in the search window, and D=m,n is a displacement vector of the specific block in the search window with respect to a zero displacement block in the search window. The block in the search window which results in the minimum error is then determined. The block in the search window which results in the minimum error may be the zero displacement block (D=0,0) or a block which is displaced from the zero displacement block by a motion vector D=m*,n*, where m*,n* is the value of m,n which results in the minimum error. The zero displacement block (i.e., D=0,0) in the search window is the 16.times.16 block which has the same location in the previous frame stored in the previous frame memory system 30 as the current block has in the current frame. If D does not equal 0,0, it means that the best match block in the search window is displaced from the zero displacement block by the motion vector m*,n*.
The MC decision unit 32 determines whether or not to use motion compensation for each current block in the current frame. The algorithm used to make the decision may be understood with help of FIG. 2. In FIG. 2, the vertical axis represents possible values of the error between the current block and the block in the search window which results in the minimum error. The horizontal axis represents possible values of the error between the current block and the D=0,0 block in the search window. The actual errors between the current block and the best match and zero displacement blocks of the search window define a point in the graph of FIG. 2. If this point is in the shaded region of FIG. 2 (excluding the decision curve) motion is detected and motion compensation is used for the current block. If the point is outside the shaded region, motion compensation is not used for the current block.
Once it is decided whether or not to use motion compensation for a current block, the Inter/Intra Decision Unit 33 decides whether to use intra-mode or inter-mode coding for the current block. If notion compensation is to be used, then the best match (i.e., minimum error) block of the search window is used for the inter/intra decision. If motion compensation is not used for the current block, then the inter/intra decision is made using the zero displacement block of the search window.
The inter/intra decision is as follows: the variance of the current block and the variance of the error between the current block and the best match or zero displacement block (depending on whether or not there is Motion Compensation) are determined. The variance (VAROR) of the current block is given by ##EQU2## In addition, the variance of the error between current and best match block or zero displacement block is given by ##EQU3##
Depending on the value of VAROR and VAR, inter or intra mode coding is utilized in accordance with FIG. 3.
The decision as to whether to use inter or intra coding is transmitted from the MC circuit to the multiplexer 12 via line 35.
When intra-mode coding for the current block is used, the current block is transmitted from the frame memory 12, via the multiplexer 14, to the DCT circuit 16 and the block is coded directly using the DCT circuit 16, the quantizer 18, and the VLC circuit 20 in the manner discussed above. The inverse quantizer 28 and IDCT circuit 29 are used to reconstruct the block for storage in the previous frame memory 30.
When the inter-mode is used, the best match or zero displacement block (depending on whether or not Motion Compensation is used) from the previous frame is retrieved from the previous frame memory system 30 and is filtered by the loop filter 38, which filter performs a smoothing function. The subtractor 39 is then used to obtain the difference between the current block and best match or zero displacement block from the previous frame. The difference is then transmitted from the subtractor 39, via the multiplexer 14, to the DCT circuit 16. The difference is transformed using the DCT circuit 16. The resulting transform coefficients are then thresholded and quantized using the quantizer circuit 18. The resulting coefficients are coded using the VLC 20 and transmitted via the multiplexer 22, the buffer 24, and the channel 26 to a destination.
The difference is reconstructed using the inverse quantizer 28 and IDCT circuit 29.
When inter-mode coding is used, the output of the filter 38 is transmitted via the multiplexer 37 to the adder 34.
The adder 34 combines the reconstructed difference at the output of the IDCT circuit 29 with the output of the filter 38 to reconstruct the current block. The current block is then stored in the previous frame memory system 30.
There is also transmitted to the destination via line 35, multiplexer 22, buffer 24, and channel 26 an indication of whether inter or intra-mode coding is being used for a block. This indication is also transmitted to the multiplexer 14 so that the multiplexer can determine whether to transmit to the DCT circuit 16, the circuit block from the input frame memory 12 or the difference from the subtractor 39. In addition, there is transmitted to the destination, via line 36, the multiplexer 22, the buffer 24 and the channel 26, the best match displacement vector when motion compensation is being used or an indication that the zero displacement block from the search window is being used.
In a typical application, one frame is entirely intra-mode coded and the alternate frame is coded using a predictive mode in the manner described above.
The use of motion compensation in the video coder has a number of significant advantages. Based on persistence of vision, a television signal has to be scanned at a speed of 30 frames/sec. However, in many applications, such as video conferencing there is a large amount of redundancy between frames. The use of motion compensation in the manner described above, reduces this redundancy and allows the video signal to be highly compressed. A variety of different algorithms can be used to estimate the motion between a block of pixels of the current frame and the previous frame which is stored in the previous frame memory 30 of FIG. 1. For example, a pixel recursive algorithm is disclosed in A. N. Netravali et al., "Motion Compensation Television Coding: Part I", BSTT, Vol. 58, pp. 631-670, March, 1979; and, K. A. Probhu et al., "Pel Recursive Motion Compensated Color Codecs", Proc ICC 82, p. 2G. 8.1-8.5, Philadelphia, Pa., June 1982). A block matching algorithm is disclosed in J. R. Jain et al., "Displacement Measurement and Its Application in Interframe Image Coding", IEEE Trans. on Comm., Vol. COM-29, p. 1799-1808, December 1981.
All of these algorithms require the retrieval of pixels of the previous frame from a previous frame memory (e.g., previous frame memory 30 of FIG. 1) and pixels from the current frame from a current frame memory (e.g., input frame memory 12 of FIG. 1). In order to code a video signal in real time (e.g., 15 or 30 frames per second) these frame memories must be accessed at high speed. The currently available Video RAMs (VRAMs) which meet the speed requirement are few in number and also very expensive.
Accordingly, it is an object of the present invention to provide a memory architecture for use in a video coder which enables motion compensation to operate in real time and which also reduces the cost of the frame memories used in the video coder. It is a further object of the invention to provide memory architecture in the video coder which permits block matching algorithms to use data in different pixel blocks repeatedly at different times.